#include <stdio.h>
#include <stdlib.h>
#include <string.h>



/* Nodo albero di huffman */
struct node{
    int value;
    char letter;
    struct node *left,*right;
};

typedef struct node Node;


/*Trova frequenza lettere*/
int * arrayFreq(char* str){
	static int counts[256] = { 0 };
	
	int i;
	size_t len = strlen(str);

	for (i = 0; i < len; i++) {
		counts[(int)(str[i])]++;
	}
	return counts;
}

/*Trova minore*/
int trovaMinore(Node *array[], int diverso)
{
	int i, minore;
	
	for(i=0;i<256;i++){
		if(array[i]->value <= 0 || i == diverso)
			continue;
		if(i==0)
			minore =i;
		else
			if(array[i]->value<array[minore]->value)
				minore = i;
			
	}
	 return minore;
}


/*Costruisce albero Huffman*/
void HuffTree(Node **tree, int *freq[])
{
	Node *temp;
	Node *array[256];
	int i, add1, add2;
	int foglie = 256;
	
	for(int i=0; i<256; i++){
		array[i] = malloc(sizeof(Node));
		array[i]->value=*freq[i];
		array[i]->letter=i;
		array[i]->left= NULL;
		array[i]->right = NULL;
	}
	
	
	while (foglie>1){
        add1= trovaMinore(array,-1);
        add2=trovaMinore(array,add1);
        temp = array[add1];
        array[add1] = malloc(sizeof(Node));
        array[add1]->value=temp->value+array[add2]->value;
        array[add1]->letter=add1+add2;
        array[add1]->left=array[add2];
        array[add1]->right=temp;
        array[add2]->value=-1;
        foglie--;
	}
	
	*tree=array[add1];

}	





int main()
{
	char *str = "Codifica di Huffman";
	int *freq =arrayFreq(str);
	
	Node *tree;
	
	HuffTree(&tree, &freq);
	
	
	
	
	return 0;
}